package leetcode.leetcode_120;

import java.util.Arrays;
import java.util.List;

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int m = triangle.get(n-1).size();
        int[][] cache = new int[n][m];
        for (int [] row :cache){
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        return dfs(triangle,0,0,cache);
    }
    public int dfs(List<List<Integer>> triangle, int i, int j,int [][]cache){
        if (triangle.size()-1== i){
            cache[i][j] = triangle.get(i).get(j);
            return triangle.get(i).get(j);
        }
        if (cache[i][j]!=Integer.MAX_VALUE){
            return cache[i][j];
        }
        cache[i][j] = Math.min(dfs(triangle,i+1,j,cache),dfs(triangle,i+1,j+1,cache))+triangle.get(i).get(j);
        return cache[i][j];
    }
}